package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/balanced-binary-tree/">平衡二叉树(Balanced Binary Tree)</a>
 * <p>给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：true
 *
 * 示例 2：
 *      输入：root = [1,2,2,3,3,null,null,4,4]
 *      输出：false
 *
 * 示例 3：
 *      输入：root = []
 *      输出：true
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中的节点数在范围 [0, 5000] 内</li>
 *     <li>-10^4 <= Node.val <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 16:24
 */
public class LC0110BalancedBinaryTree_S {
    static class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }

        private int getHeight(TreeNode node) {
            if (node == null) {
                return 0;
            }
            return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(2);
        root2.left.left = new TreeNode(3);
        root2.left.right = new TreeNode(3);
        root2.left.left.left = new TreeNode(4);
        root2.left.left.right = new TreeNode(4);

        Solution solution = new Solution();
        System.out.println(solution.isBalanced(root1));
        System.out.println(solution.isBalanced(root2));
    }
}
